package com.fanshuai.tree.segmenttree;

/**
 * 基本线段树
 * 线段树为一种二叉搜索树。每个节点表示某个区间的元素聚合的值。
 * 线段树保存某个数组的区间聚合值。根节点区间范围为0 ~ len(arr)-1。从根节点开始，每个子节点表示的区间范围二分
 * 叶节点表示区间范围为单个元素, 单个元素的聚合值为元素值本身。通过线段树可以快速计算数组任意范围的聚合值
 */
public class BaseSegmentTree<E> implements ISegmentTree<E> {
    /**
     * 数据
     */
    private E[] data;
    /**
     * 线段树
     */
    private E[] tree;

    private Merger<E> merger;

    public BaseSegmentTree(E[] data, Merger<E> merger) {
        this.merger = merger;

        this.data = (E[]) new Object[data.length];
        for (int i = 0; i < data.length; i++) {
            this.data[i] = data[i];
        }

        //线段树元素个数为4N
        tree = (E[]) new Object[data.length << 2];
        build(0, 0, data.length - 1);
    }

    /**
     * 构造线段树
     * @param treeIndex
     * @param left
     * @param right
     */
    private void build(int treeIndex, int left, int right) {
        if (left == right) {
            tree[treeIndex] = data[left];
            return;
        }

        int mid = (left + right) / 2;

        int leftChildIndex = 2 * treeIndex + 1;
        int rightChildIndex = 2 * treeIndex + 2;
        build(leftChildIndex, left, mid);
        build(rightChildIndex, mid + 1, right);

        tree[treeIndex] = merger.merge(tree[leftChildIndex], tree[rightChildIndex]);
    }

    @Override
    public void update(int index, E value) {
        if (index < 0 || index > data.length) {
            throw new IndexOutOfBoundsException("index=" + index);
        }

        data[index] = value;
        updateTree(0, 0, data.length - 1, index, value);
    }

    /**
     * 更新线段树  线段树二分，递归遍历，找到叶节点并更新。然后在回溯的过程中更新非叶节点
     * @param treeIndex
     * @param left
     * @param right
     * @param index
     * @param value
     */
    private void updateTree(int treeIndex, int left, int right, int index, E value) {
        if (left == right) {
            tree[treeIndex] = value;
            return;
        }

        int mid = (left + right) / 2;
        int leftChildIndex = 2 * treeIndex + 1;
        int rightChildIndex = 2 * treeIndex + 2;

        if (index >= mid + 1) {//更新右子树
            updateTree(rightChildIndex, mid + 1, right, index, value);
        } else {//更新左子树
            updateTree(leftChildIndex, left, mid, index, value);
        }

        tree[treeIndex] = merger.merge(tree[leftChildIndex], tree[rightChildIndex]);
    }

    @Override
    public E query(int L, int R) {
        if (L < 0) {
            L = 0;
        }
        if (R > data.length - 1) {
            R = data.length - 1;
        }

        return queryTree(0, 0, data.length - 1, L, R);
    }

    /**
     * 区间查询
     * @param treeIndex
     * @param left
     * @param right
     * @param queryLeft
     * @param queryRight
     * @return
     */
    private E queryTree(int treeIndex, int left, int right, int queryLeft, int queryRight) {
        //查询子区间与当前区间重合，直接返回
        if (queryLeft == left && queryRight == right) {
            return tree[treeIndex];
        }

        /**
         * 拆分区间
         *
         * 如果查询区间位于左子区间，直接查询左子区间
         * 查询区间位于右子区间，查询右子区间
         * 查询区间同时位于左、右子区间，同时查询左右子区间，将结果聚合
         */
        int mid = (left + right) / 2;
        int leftChildIndex = 2 * treeIndex + 1;
        int rightChildIndex = 2 * treeIndex + 2;

        if (queryRight <= mid) {
            return queryTree(leftChildIndex, left, mid, queryLeft, queryRight);
        } else if (queryLeft >= mid + 1) {
            return queryTree(rightChildIndex, mid + 1, right, queryLeft, queryRight);
        } else {
            E leftValue = queryTree(leftChildIndex, left, mid, queryLeft, mid);
            E rightValue = queryTree(rightChildIndex, mid + 1, right, mid + 1, queryRight);
            return merger.merge(leftValue, rightValue);
        }
    }

    @Override
    public void update(int L, int R, E value) {
        if (L < 0 || L > data.length) {
            throw new IndexOutOfBoundsException("index=" + L);
        }
        if (R < 0 || R > data.length) {
            throw new IndexOutOfBoundsException("index=" + R);
        }

        for (int i = L; i <= R; i++) {
            update(i, value);
        }
    }
}
